import java.util.PriorityQueue;
import java.util.Queue;

class MedianFinder {
    private Queue<Long> small = new PriorityQueue();
    private Queue<Long> large = new PriorityQueue();

    /** initialize your data structure here. */
    public MedianFinder() {

    }

    public void addNum(int num) {
        large.add((long) num);
        small.add(-large.poll());
        if (large.size() < small.size())
            large.add(-small.poll());
    }

    public double findMedian() {
        return large.size() > small.size() ? large.peek() : (large.peek() - small.peek()) / 2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */